// top down
var fib = function (N) {
    if (N <= 1) {
        return N
    }
    const cache = []
    cache[0] = 0
    cache[1] = 1

    function memoize(number) {
        // 有值则直接取
        if (cache[number] !== undefined) {
            return cache[number]
        }
        // 没有值需要递归计算
        cache[number] = memoize(number - 1) + memoize(number - 2)
        return cache[number]
    }

    const result = memoize(N)
    return result
}

// bottom up
var fib2 = function (N) {
    if (N <= 1) {
        return N
    }

    const cache = []
    cache[0] = 0
    cache[1] = 1

    for (let i = 2; i <= N; i++) {
        cache[i] = cache[i - 1] + cache[i - 2]
    }

    return cache[N]
}

// 空间复杂度优化
var fib3 = function (N) {
    if (N <= 1) {
        return N
    }

    let prev2 = 0
    let prev1 = 1

    for (let i = 2; i <= N; i++) {
        let temp = prev1 + prev2
        prev2 = prev1
        prev1 = temp
    }

    return prev1
}